package sort;

//采用三路划分的操作将数据划为小于，等于，大于
public class QuickSort2 {

	public static void main(String[] args) {
		 int[] a =
		 {23,21,25,19,35,31,65,34,25,42,3,31,29,22,29,22,25,25,34,26,25};
//		int[] a = { 7, 25, 25, 43, 26, 25 };
		for (int i : a) {
			System.out.print(i + " ");
		}
		System.out.println();
		quickSort(a, 0, a.length - 1);
		// quickSort3Way(a,0, a.length - 1);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}

	// 三路划分的思想大致上就是找到相等的元素，在左边的话就将元素放置左边的左边，右边的话就是右边的右边
	// 相等区 ||小于区||大于区||相等区 ||元素
	// 最后当左指针与右指针相遇时就将数据调换到中间
	// 形成 小 于区||相等区||大于区
	public static void quickSort(int[] a, int left, int right) {
		if (left >= right || a == null)
			return;
		int i = left, j = right - 1; // 定义初始指针的位置
		int equalLeft = left - 1, equalRight = right; // 定义相等的元素初始位置
		int partNum = a[right]; // 确定划分的元素为最右端元素
		while (true) {
			// 自左向右查找
			while (a[i] < partNum) {
				i++;
			}
			// 只有j大于i才自右向左查找
			while (j >= i && a[j] > partNum) {
				j--;
			}
			if (i >= j)
				break;
			if (i < j) {
				// 当两个循环都退出并且i小于j的时候，即说明找到交换的值了
				MaoPaoSort.swap(a, i, j);
			}
			// 注意，有可能两者同时为partNum。那样就交换两次
			if (a[i] == partNum) {
				equalLeft++;
				MaoPaoSort.swap(a, equalLeft, i);
			}
			if (a[j] == partNum) {
				equalRight--;
				MaoPaoSort.swap(a, equalRight, j);
			}
		}
		// 有一个问题就是像7 25 43 26 25这个序列（这是一种序列），最后a[i]=25，而a[j]=7，退出了循环
		// 故break后面的步骤都没有运行，导致equalLeft和equalRight的值最后都没有发生过变化。
		// 下面的那两个交换的循环也就不会执行了
		// 最后交换a[i]和a[right]的值，i即为所选元素的位置
		// if(a[i]==a[right]){
		// equalRight--;
		// }else {
		MaoPaoSort.swap(a, i, right);
		// }
		j = i - 1;
		i += 1;
		for (int k = left; k <= equalLeft; k++, j--) {
			MaoPaoSort.swap(a, k, j);
		}
		for (int k = right - 1; k >= equalRight; k--, i++) {
			MaoPaoSort.swap(a, k, i);
		}
		for (int l : a) {
			System.out.print(l + " ");
		}
		System.out.println("rightpos " + i + " leftpos " + j);
		quickSort(a, left, j); // 对左半部分操作
		quickSort(a, i, right); // 对右半部分操作
	}

	public static void quickSort3Way(int a[], int left, int right) {
		if (left < right) {
			int x = a[right];
			int i = left - 1, j = right, p = left - 1, q = right;
			for (;;) {
				while (a[++i] < x) {
				}
				while (a[--j] > x) {
					if (j == left)
						break;
				}
				if (i < j) {
					MaoPaoSort.swap(a, i, j);
					if (a[i] == x) {
						p++;
						MaoPaoSort.swap(a, p, i);
					}
					if (a[j] == x) {
						q--;
						MaoPaoSort.swap(a, q, j);
					}
				} else
					break;
			}
			MaoPaoSort.swap(a, i, right);
			j = i - 1;
			i = i + 1;
			for (int k = left; k <= p; k++, j--)
				MaoPaoSort.swap(a, k, j);
			for (int k = right - 1; k >= q; k--, i++)
				MaoPaoSort.swap(a, i, k);

			for (int l : a) {
				System.out.print(l + " ");
			}
			System.out.println("rightpos " + i + " leftpos " + j);
			quickSort3Way(a, left, j);
			quickSort3Way(a, i, right);
		}
	}
}
